#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*
    线性表：1. 有限的序列 2. 序列中的每一个元素都有唯一的前驱和后继，除了开头和结尾两个结点
    顺序表：分配一块连续的内存去存放这些元素，例如数组。。。

    链表： 内存是不连续的，元素会各自被分配一块内存，内存和内存之间用 指针 进行相连

    data(数据域),next(指针域)
    最后一个节点指向NULL
    
    单链表操作：
    1. 增加
        1. 头插法
        2. 尾插法
    2. 删除：只需要找到对应节点，将对应结点的前一个结点指向这个节点的后继，之操作一个指针

    为了方便操作 这里我们带 头结点 ：它的数据域可以保存链表元素个数
*/

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* initList()
{
    Node* list = (Node *)malloc(sizeof(Node));
    list->data = 0;
    list->next = NULL;
    return list;// 返回头节点
}

// 头插
void headInsert(Node * list, int data)
{
    Node * node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = list->next;
    list->next = node;
    list->data++;
}

// 尾插
void tailInsert(Node * list, int data)
{
    Node * head = list;// 保存头节点地址
    Node * node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    // 如果链表为空，直接将节点设为第一个节点
    if (list->next == NULL) 
    {
        list->next = node;
    } 
    else 
    {
        list = list->next;
        // 找到链表的尾部
        while(list->next) 
        {
            list = list->next;
        }
        list->next = node;
    }

    head->data++; // 计数加一
}

// 删除
void delete(Node * list, int data)
{
    Node * pre = list;// 前一个结点
    Node * current = list->next;
    while(current)
    {
        if (current -> data == data)
        {
            pre->next = current->next;
            free(current);
            current = pre->next; // 更新 current
            list->data--; // 计数减一
            continue; // 删除后继续检查下一个节点
        }
        pre = current;
        current = current->next;
    }
}

// 遍历
void printList(Node* list)
{
    list = list->next;
    while(list)
    {
        printf("%d", list->data);
        list = list->next;
    }
    printf("\n");
}

int main()
{
    Node * list = initList();
    headInsert(list, 1);
    headInsert(list, 2);
    headInsert(list, 3);
    headInsert(list, 4);
    headInsert(list, 5);
    tailInsert(list, 6);
    tailInsert(list, 7);
    tailInsert(list, 8);
    tailInsert(list, 9);
    tailInsert(list, 0);
    printList(list);
    delete(list,5);
    delete(list,7);
    printList(list);


    return 0;
}